package com.yj.question_project.question;

import com.yj.question_project.domain.MetroLine;
import com.yj.question_project.domain.VNode;
import com.yj.question_project.utils.NodeUtils;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.stream.Collectors;

/**
 * @Auther: starsky1
 * @Date: 2024/01/10 20:52
 * @Description: todo
 */
public class Ques2 {
    private static Map<Integer, VNode> stationMap = new HashMap<>(50);
    private static Map<String, Integer> stationIdMap = new HashMap<>(50);
    private static Map<String, MetroLine> lineMap = new LinkedHashMap<>(20);
    private static int min = Integer.MAX_VALUE;
    private static char[] AZ = new char[]{'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};

    public static void main(String[] args) {
        NodeUtils.initData(stationMap, stationIdMap, lineMap);
        Map<String, VNode> codeToNodeMap = new HashMap<>(stationMap.size());
        StringBuilder sb = new StringBuilder();
        for (Map.Entry<String, MetroLine> entry : lineMap.entrySet()) {
            sb.delete(0,sb.length());
            final MetroLine metroLine = entry.getValue();
            Integer index  = entry.getKey().indexOf("line");
            sb.append(metroLine.getLineName()).append(": ");
            int i = 0;
            for (VNode station : metroLine.getStations()) {
                String staCode = entry.getKey().substring(index+4)
                        + AZ[i%26] + (i/26>0?i/26:"");
                sb.append(station.getStaName()).append("[")
                        .append(staCode).append("]").append(" -> ");
                codeToNodeMap.put(staCode, station);
                i++;
            }
            System.out.println(sb.substring(0,sb.length()-4));
        }
        Scanner sc = new Scanner(System.in);
        while(true) {
            min = Integer.MAX_VALUE;
            System.out.println("请输入起点编号和终点编号，输入0结束程序");
            System.out.print("起点: ");
            String start = sc.next();
            if(start.equals("0")) {
                sc.close();
                break;
            }
            System.out.print("终点: ");
            String end = sc.next();
            final VNode startNode = codeToNodeMap.get(start);
            if(startNode == null) {
                System.out.println("起点不存在");
                continue;
            }
            final VNode endNode = codeToNodeMap.get(end);
            if(endNode == null) {
                System.out.println("终点不存在");
                continue;
            }
            List<List<VNode>> paths = getAllPaths(startNode.getStaId(), endNode.getStaId());
            paths = paths.stream().filter(path -> path.size()<=min).collect(Collectors.toList());
            int i = 0;
            for (List<VNode> path : paths) {
                sb = new StringBuilder();
                for (VNode vNode : path) {
                    sb.append(vNode.staNameToString()).append(" -> ");
                }
                System.out.printf("价格: %.1f, 路径%d: %s \n", (path.size()-1)*0.5,++i, sb.substring(0, sb.length()-4));
            }
            System.out.println(paths.size());
        }
    }

    public static List<List<VNode>> getAllPaths(Integer start, Integer end) {
        List<List<VNode>> paths = new ArrayList<>();
        List<VNode> path = new ArrayList<>();
        path.add(stationMap.get(start));
        dfs(stationMap.get(start), end, new HashSet<>(), path, paths);
        return paths;
    }

    public static void dfs(VNode curr, int end, Set<Integer> visited,
                           List<VNode> path, List<List<VNode>> paths) {
        if(curr == null) {
            return;
        }
        if(curr.getStaId() == end) {
            paths.add(new ArrayList<>(path));
            min = Math.min(min, path.size());
            return;
        }
        for (VNode neighbor : curr.getRelateNodes()) {
            if(!visited.contains(neighbor.getStaId())) {
                if(path.size()+1>min) {
                    return;
                }
                path.add(neighbor);
                visited.add(neighbor.getStaId());
                dfs(neighbor, end, visited, path, paths);
                path.remove(path.size()-1);
                visited.remove(neighbor.getStaId());
            }
        }
    }

}
